package edu.pku.sei.transformation.editor.model.base;

import java.util.ArrayList;
import java.util.Collection;

public class ListNameTable implements INameSpace {
	private ArrayList<NamedElement> datas = new ArrayList<NamedElement>();

	@Override
	public Collection<NamedElement> getAllElements() {
		return datas;
	}

	@Override
	public NamedElement getElement(String name) {
		int index = getPosition(name);
		NamedElement element = datas.get(index);
		if (element.getName().equals(name))
			return element;
		else
			return null;
	}

	@Override
	public boolean registerName(NamedElement element) {
		String name = element.getName();
		int index = getPosition(name);
		NamedElement currentElement = datas.get(index);
		if (currentElement.getName().equals(name))
			return false;
		else {
			datas.add(index, element);
			return true;
		}

	}

	@Override
	public boolean unregisterName(NamedElement element) {
		String name = element.getName();
		return unregisterName(name);
	}

	@Override
	public boolean unregisterName(String name) {
		int index = getPosition(name);
		NamedElement currentElement = datas.get(index);
		if (currentElement.getName().equals(name)) {
			datas.remove(index);
			return true;
		} else {
			return false;
		}
	}

	/**
	 * compare to string, and return if s1 is less than s2
	 * 
	 * @param s1
	 * @param s2
	 * @return true if s1 < s2; false if s1 >= s2
	 * 
	 */
	private boolean lessThan(String s1, String s2) {
		char[] s1b = s1.toCharArray();
		char[] s2b = s2.toCharArray();
		boolean s1ShorterThenS2 = s1.length() < s2.length();
		int length = s1ShorterThenS2 ? s1.length() : s2.length();

		for (int i = 0; i < length; i++) {
			if (s1b[i] > s2b[i])
				return false;
			else if (s1b[i] < s2b[i])
				return true;
		}

		return s1ShorterThenS2;
	}

	private int getPosition(String name) {
		return getPosition(name, 0, datas.size());
	}

	private int getPosition(String s, int start, int end) {
		if (start >= end)
			return start;

		int middle = (start + end) / 2;
		String middleName = datas.get(middle).getName();

		if (lessThan(middleName, s))
			return getPosition(s, start, middle);
		else if (middleName.equals(s))
			return middle;
		else
			return getPosition(s, middle + 1, end);
	}

}
